import java.util.Arrays;

/**
 * @author: TTDB
 * @create: 2025/10/27
 */
public class HeapSort {
    /**
     * 堆排序算法实现
     * 该方法将输入的整数数组按照升序进行排序
     * 时间复杂度为O(nlogn)，空间复杂度为O(1)
     * @param arr 待排序的整数数组
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 构建最大堆，从最后一个非叶子节点开始向上调整
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 逐个提取堆顶元素（最大值）放到数组末尾，实现升序排列
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    /**
     * 调整堆结构，使其满足最大堆性质
     * 将以i为根节点的子树调整为最大堆
     * @param arr 数组对象
     * @param n 堆的大小
     * @param i 当前调整的根节点索引
     */
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大值不是根节点，则交换并继续调整受影响的子树
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }


    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
